"""LCR 094. 分割回文串 II(https://leetcode.cn/problems/omKAoA/description/)"""


class Solution:
    def minCut(self, s: str) -> int:
        # 1
        n = len(s)
        # 表示从i到j的索引里面是回文串
        g = [[True] * n for _ in range(n)]

        # 2.
        # 外层循环作为滑动窗口左边界
        # 从最后一个元素到-1，步长是-1，这里逆序一直到最开始
        for i in range(n - 1, -1, -1):
            # 内层循环作为滑动窗口右边界，从窗口最左面一路遍历到最右面
            for j in range(i + 1, n):
                # 这里相等表示找到切割点
                # 前：设置gij为flase表示i-j序列不是一个回文串，所以标记false表示这里不是一个切割点
                # 后： 这里的i+1 表示前一个窗口的左边界，j-1 表示前一个窗口的右边界，
                # 注意回文串的意思是指对称字符串，因为这里是从最小开始的，所以每次只确认，内部包含的最近一组对称即可
                # 开始打标记，这里表示i-j序列是一个回文串，所以标记true表示这里是一个切割点
                # 里面的夹心是回文串，加上两层相同的外壳依旧是回文串
                g[i][j] = (s[i] == s[j]) and g[i + 1][j - 1]

        # 通过上面的操作任意长度的索引里面是否是回文串已经标记好

        # 3.动态规划
        f = [float("inf")] * n
        # 这里的i是右边界
        for i in range(n):
            # f[i] 表示从字符串开头到第 i 个字符的最小切割次数。
            if g[0][i]:
                f[i] = 0
            else:
                # 内层循环j作为左边界，从左到右遍历
                # 可以进入到这里就说明从开始到这里不是一个回文串，所以对于每个窗口循环遍历，试图找到那个切割点
                """假设g[0][2] = False，进入内层循环：
                j = 0：
                    检查 g[1][2]：
                    g[1][2] = False，所以不更新 f[2]。
                j = 1：继续
                    检查 g[2][2]：
                    g[2][2] = True，所以更新 f[2]：
                """
                for j in range(i):
                    # 如果内部左边界到当前窗口的右边界可以切割（即发现了一个回文串）
                    # 这里i是当前的右窗口，
                    if g[j + 1][i]:
                        # 这里比较左面窗口+1次（中间切一刀）和当前窗口的切割次数，取最小值
                        f[i] = min(f[i], f[j] + 1)

        return f[n - 1]

    def myminCut(s: str) -> int:
        n = len(s)
        # 记录从开始到当前位置的最小切割次数
        dp = [0] * n
        # 是否回文串
        palindrome = [[False] * n for _ in range(n)]

        # j左窗口，i右窗口
        for i in range(n):
            min_cut = i
            for j in range(i + 1):
                # 从左到右，保证首尾相同，当子串的长度小于等于 2 时，即只有一个字符或者两个相同的字符时，该子串一定是回文串
                if s[j] == s[i] and (i - j < 2 or palindrome[j + 1][i - 1]):
                    palindrome[j][i] = True
                    # j==0即开始位置，直接0；else 表示从上一个位置+1次切割
                    min_cut = 0 if j == 0 else min(min_cut, dp[j - 1] + 1)
            dp[i] = min_cut

        return dp[-1]


test = Solution()
print(test.minCut("aabgsafidsgfggwfag"))
print(test.myminCut("aabgsafidsgfggwfag"))
